RFID systems can be used to track, identify, and/or locate items. Such systems conventionally include RFID tags that are affixed to the items, an RFID reader that includes a transmit antenna to send activation signals to the RFID tags and a receive antenna to receive backscattered response signals from the activated tags. As a limitation, many RFID systems require that the RFID reader be within close proximity to the activated RFID tag in order to correctly receive the response signal. The backscattered response signal is more vulnerable to interferences as the distance between the RFID tag and the receive antenna increases. Further, the backscattered response signal may travel multiple paths to the receiver antenna creating multipath distortion.
The theory of compressive sampling, also known as compressed sensing or CS, is a novel sensing/sampling paradigm that allows one to recover signals from far fewer samples or measurements than once thought to be possible. The following overview of CS is largely drawn from Emmanuel J. Candes and Michael B. Wakin, An Introduction to Compressive Sampling, IEEE Signal Processing Magazine 21 (March 2008).
CS in practice allows for designing sampling protocols that allow for capturing less data while still maintaining the ability to reconstruct the signal of interest. The two fundamental requirements for CS protocols are that (1) the signals of interest must be “sparse” and (2) the sensing modality must have a sufficient degree of “incoherence”.
By way of background, sparsity expresses the idea that the “information rate” of a continuous time signal may be much smaller than suggested by its bandwidth, or that a discrete-time signal depends on a number of degrees of freedom, which is comparably much smaller than its (finite) length. More precisely, CS exploits the fact that many natural signals are sparse or compressible in the sense that they have concise representations when expressed in an appropriate basis.
Incoherence extends the duality between time and frequency and expresses the idea that objects have a sparse representation in one domain can be spread out in the domain in which they are acquired, just as a Dirac or spike in the time domain is spread out in the frequency domain. Put differently, incoherence says that unlike the signal of interest, the sampling/sensing waveforms are capable of having an extremely dense representation in an appropriate domain.
Sparsity
Systems that perform CS typically are faced with the problem in which information about a signal f(t) is obtained by linear functionals recording the values:yk=f,φk
In a standard configuration, the objects that the system acquires are correlated with the waveform φk (t). If the sensing waveforms are Dirac delta functions (spikes), for example, then y is a vector of sampled values of f in the time or space domain. If the sensing waveforms are sinusoids, then y is a vector of Fourier coefficients; this is the sensing modality used in magnetic resonance imaging MRI.
Systems can apply CS to recover information in undersampled situations. Undersampling refers to a circumstance in which the number M of available measurements is much smaller than the dimension N of the signal f. In such situations, a CS protocol is tasked with solving an underdetermined linear system of equations. Letting A denote the M×N sensing or measurement matrix with the vectors φ*1, . . . , φ*M as rows (a* is the complex transpose of a), the process of recovering f ϵN from y=AfϵM is ill-posed in general when M<N: there are infinitely many candidate signals for f. Shannon's theory indicates that, if f(t) has low bandwidth, then a small number of (uniform) samples will suffice for recovery. Using CS, signal recovery can actually be made possible using a broader class of signals.
Many natural signals have concise representations when expressed in a convenient basis. Mathematically speaking, a vector fϵN can be expanded in an orthonormal basis Ψ=[ψ1ψ2 . . . ψN] as follows:
      f    ⁡          (      t      )        =            ∑              i        =        0            N        ⁢                  x        i            ⁢                        ψ          i                ⁡                  (          t          )                    where x is the coefficient sequence of f, xi=<f,ψk>.
It can be convenient to express f as Ψ (where Ψ is the N×N matrix with ψ1, . . . , ψn as columns). The implication of sparsity is now clear: when a signal is a sparse expansion, the small coefficients can be discarded without much perceptual loss. Formally, consider fs (t) obtained by keeping only the terms corresponding to the S largest values of (xi). By definition fs:=Ψxs, where xs is the vector of coefficients (xi) with all but the largest S set to zero. This vector is sparse in a strict sense since all but a few of its entries are zero. Since Ψ is an orthonormal basis, ∥f−fS∥=∥x−xS∥t2, and if x is sparse or compressible in the sense that the sorted magnitudes of the (xi) decay quickly, then x is well approximated by xs and, therefore, the error ∥f−fs∥t2 is small. In plain terms, one can “throw away” a large fraction of the coefficients without much loss. As can be appreciated, sparsity is a fundamental modeling tool which permits efficient fundamental signal processing; e.g., accurate statistical estimation and classification, efficient data compression, etc. Sparsity has more surprising and far-reaching implications, however, which is that sparsity has significant bearing on the acquisition process itself. Sparsity determines how efficiently one can acquire signals nonadaptively.
Incoherent Sampling
Consider a pair (Φ, Ψ) of orthonormal bases or orthobases of N. The first basis Φ is used for sensing the object f and the second Ψ is used to represent f. The coherence between the sensing basis Φ and the representation basis Ψ is
      μ    ⁡          (              Φ        ,        Ψ            )        =            N        ⁢                  max                              1            ≤            k                    ,                      j            ≤            N                              ⁢                                〈                                    φ              k                        ,                          ψ              j                                〉                            
In plain English, coherence measures the largest correlation between any two elements of Φ and Ψ. If Φ and Ψ contain correlated elements, the coherence is large. Otherwise, it is small. As for how large and how small, it follows from linear algebra that μ(Φ, Ψ)ϵ[1, √N].
Compressive sampling is mainly concerned with low coherence pairs of bases. Such bases include the time frequency pair where Φ is the canonical or spike basis and Ψ is the Fourier basis, and wavelet bases for Ψ and noiselet basis for Φ. Random matrices are largely incoherent with any fixed basis Ψ. Select an orthobasis Φ uniformly at random, then with high probability, the coherence between Φ and Ψ is about √(2 log N). In terms of hardware cost and complexity, it is desirable if the signal basis, Ψ, does not need to be known a priori in order to determine a viable sensing matrix Φ. Fortunately, random sensing matrices with sufficient sample size exhibit low coherence with any fixed basis. This means that a random sensing matrix can acquire sufficient measurements to enable signal reconstruction of a sparse signal without knowing a priori the proper basis Ψ for the signal.
Undersampling and Sparse Signal Recovery
Ideally, the N coefficients of f are observed, but in reality a CS system can only observe a subset of these and collect the datayk=f,Φk,kϵM where Mϵ[1, . . . , n] is a subset of cardinality M<N.
With this information, a conventional approach is to recover the signal by I1-norm minimization. Essentially, for all objects consistent with the data, find the object with the coefficient sequence that minimizes the I1-norm. The use of the I1-norm as a sparsity-promoting function traces back several decades. A leading early application was reflection seismology, in which a sparse reflection function (indicating meaningful changes between subsurface layers) was sought from bandlimited data. However I1-norm minimization is not the only way to recover sparse solutions; other methods, such as greedy algorithms, or Orthogonal Matching Pursuit can also be utilized.
In view of the above, CS suggests a very concrete acquisition protocol: sample nonadaptively in an incoherent domain and invoke linear programming after the acquisition step. Following this protocol enables the acquisition of a signal in a compressed form. A decoder can then “decompress” this data.